﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using InformationRetrieval.Wildcard;
using InformationRetrieval.Normalization;
using System.IO;
using InformationRetrieval.Tokenizer;

namespace InformationRetrieval.Indexer
{
    /// <summary>
    /// Implements an in-memory inverted index with the ability to perform
    /// boolean queries and to resolve wildcard queries.
    /// </summary>
    public class BooleanWildcardInvertedIndex : IInvertedIndex
    {
        #region Fields
        private Dictionary<string, SortedSet<int>> _index = new Dictionary<string, SortedSet<int>>();
        private Dictionary<int, string> _documents = new Dictionary<int, string>();
        private HashSet<string> _documentNames = new HashSet<string>();
        private IWildcardIndex _wildcardIndex = null;
        private INormalizer _normalizer = null;
        #endregion

        #region Constructor
        /// <summary>
        /// Creates a new BooleanWildcardInvertedIndex with neither wildcard
        /// indexer nor normalizer.
        /// </summary>
        public BooleanWildcardInvertedIndex() : this(null, null) { }

        /// <summary>
        /// Creates a new BooleanWildcardInvertedIndex with the specified wildcard
        /// indexer, but no normalizer
        /// </summary>
        /// <param name="wildcardIndex">A wildcard index or null</param>
        public BooleanWildcardInvertedIndex(IWildcardIndex wildcardIndex) : this(wildcardIndex, null) { }    

        /// <summary>
        /// Creates a new BooleanWildcardInvertedIndex with the specified normalizer,
        /// but no wildcard index
        /// </summary>
        /// <param name="normalizer">A normalizer or null</param>
        public BooleanWildcardInvertedIndex(INormalizer normalizer) : this(null, normalizer) { }

        /// <summary>
        /// Creates a new BooleanWildcardInvertedIndex with the specified wildcard
        /// indexer and normalizer.
        /// </summary>
        /// <param name="wildcardIndex">A wildcard index or null</param>
        /// <param name="normalizer">A normalizer or null</param>
        public BooleanWildcardInvertedIndex(IWildcardIndex wildcardIndex, INormalizer normalizer)
        {
            _wildcardIndex = wildcardIndex ?? new DummyWildcardIndex();
            _normalizer = normalizer ?? new DummyNormalizer();
        } 
        #endregion

        #region Add
        /// <summary>
        /// Adds a new document to the index. The (un-normalized) tokens and
        /// the document name have to be provided. If the index already 
        /// contains a document with the same name, the document is silently
        /// ignored.
        /// </summary>
        /// <param name="tokens">Sequence of unnormlized tokens comprising
        /// the document</param>
        /// <param name="documentName">Unique document name</param>
        public void AddDocument(string documentName, IEnumerable<PositionedToken> documentTokens)
        {
            //Filter out duplicate documents
            if (!_documentNames.Contains(documentName))
            {
                //Get unique document ID
                int documentId = _documents.Count + 1;
                _documents.Add(documentId, documentName);
                _documentNames.Add(documentName);

                //Normalize tokens and add them to the inverted index
                //Only index the token itself and discard any info on its position
                foreach (string term in documentTokens.Select(x => _normalizer.Normalize(x.Token.ToLower())))
                {
                    if (_index.ContainsKey(term))
                        _index[term].Add(documentId);
                    else
                        _index[term] = new SortedSet<int> { documentId };

                    //Add normalized token to the wildcard index, if present
                    _wildcardIndex.AddTerm(term);
                }
            }
        }
        #endregion

        #region Find
        /// <summary>
        /// Finds all documents in the inverted index that match the query.
        /// The query may contain an arbitrary number of search words. Each
        /// search word may be linked by either 'and' or 'or'. If no boolean
        /// link is specified, it is assumed to be 'or'.
        /// Each search word may contain asterisks '*'; this will cause a 
        /// wildcard search if a wildcard index has been configured.
        /// </summary>
        /// <param name="query">Query string</param>
        /// <returns>Sequence of matching document names and their positions.
        /// This index does not actually support positional searches, so the
        /// reported term position is always '0'</returns>
        public IEnumerable<KeyValuePair<string, InformationRetrieval.Indexer.InvertedIndex.Posting>> Find(string searchQuery)
        {
            // Split and normalize query tokens
            string[] queryTokens = searchQuery.ToLower().Split(new[] { ' ' }, StringSplitOptions.RemoveEmptyEntries);
            for (int i = 0; i < queryTokens.Length; i++)
            {
                if (queryTokens[i] != "and" && queryTokens[i] != "or")
                {
                    queryTokens[i] = _normalizer.Normalize(queryTokens[i]);
                }
            }

            // Parse boolean AND/OR links
            List<QueryToken> parsedQuery = new List<QueryToken>();
            string tokenType = "or";
            foreach (string queryToken in queryTokens)
            {
                if (queryToken == "and" || queryToken == "or")
                    tokenType = queryToken;
                else
                {
                    parsedQuery.Add(new QueryToken { Token = queryToken, QueryType = tokenType });
                    tokenType = "or";
                }
            }

            // Find matching documents
            SortedSet<int> results = new SortedSet<int>();
            SortedSet<int> wildcardPostingList = null;
            foreach (var token in parsedQuery)
            {
                SortedSet<int> tempPostingList = new SortedSet<int>();
                SortedSet<int> postingList = new SortedSet<int>();

                // Find the posting list for the current term; if the term
                // contains wildcards, resolve them 
                foreach (var term in _wildcardIndex.Find(token.Token))
                {
                    if (!_index.TryGetValue(term, out wildcardPostingList))
                        wildcardPostingList = new SortedSet<int>();
                    postingList.UnionWith(wildcardPostingList);
                }

                // Merge the posting list for the current term with the global
                // results posting list
                if (token.QueryType == "and")
                    results.IntersectWith(postingList);
                else if (token.QueryType == "or")
                    results.UnionWith(postingList);
            }

            // Return the document name and a dummy posting list for each matching document
            return (from r in results
                    select new KeyValuePair<string, InformationRetrieval.Indexer.InvertedIndex.Posting>(
                        _documents[r],
                        new InformationRetrieval.Indexer.InvertedIndex.Posting(
                            1,
                            new SortedSet<int> { 0 }
                        ))
                    );
        }
        
        #endregion

        #region Persist
        /// <summary>
        /// Dummy implementation; does not persist the index
        /// </summary>
        public void Persist()
        {
            //Dummy implementation
        } 
        #endregion

        #region Statistics

        /// <summary>
        /// Number of documents in the inverted index
        /// </summary>
        public int DocumentCount { get { return _documents.Count; } }

        /// <summary>
        /// Number of unique, normalized terms in the inverted index
        /// </summary>
        public int TermCount { get { return _index.Count; } }

        /// <summary>
        /// Average length of the posting lists
        /// </summary>
        public int AvgPostingListLength
        {
            get
            {
                if (_index.Count > 0)
                    return (int)_index.Values.Average(x => x.Count);
                else return 0;
            }
        }

        /// <summary>
        /// Key-Value-Pair of the term with the longest posting list and
        /// the length of its posting list
        /// </summary>
        public KeyValuePair<string, int> MaxPostingListLength
        {
            get
            {
                if (_index.Count > 0)
                    return _index
                        .OrderByDescending(x => x.Value.Count)
                        .Select(x => new KeyValuePair<string, int>(x.Key, x.Value.Count))
                        .FirstOrDefault();
                else return new KeyValuePair<string, int>("Index Empty", 0);
            }
        }

        /// <summary>
        /// List of the 50 most common terms in the index, i.e. the terms
        /// with the longest posting lists
        /// </summary>
        public IEnumerable<string> MostCommonTerms50
        {
            get
            {
                return (from kvp in _index
                        orderby kvp.Value.Count descending
                        select kvp.Key).Take(50);
            }
        }

        /// <summary>
        /// List of the 50 least common terms in the index, i.e. the terms
        /// with the shortest posting lists
        /// </summary>
        public IEnumerable<string> LeastCommonTerms50
        {
            get
            {
                return (from kvp in _index
                        orderby kvp.Value.Count
                        select kvp.Key).Take(50);
            }
        }

        #endregion

        #region Inner Classes
        /// <summary>
        /// Represents one token (i.e. one search word) of a query, including
        /// how it is to merged with the preceding tokens (i.e. 'and' / 'or')
        /// </summary>
        private class QueryToken
        {
            /// <summary>
            /// Search word
            /// </summary>
            public string Token { get; set; }

            /// <summary>
            /// 'and' or 'or'
            /// </summary>
            public string QueryType { get; set; }
        }
        #endregion
    }
}
